#ifndef __LINKGRAPH__
#define __LINKGRAPH__
#include <iostream>
#include <queue>
//the implementation of graph with adjacency links 
class LinkGraph{
public:
	LinkGraph(int num):max_node_num_(num){}
	~LinkGraph();
	void CreatGraph();
	void DeepFirstTraverse(int index);
	void BreathFirstTraverse(int index);
protected:
	struct Node{
		int data;
		Node * next;
	};
private:
	Node ** graph_;// the adjacency list
	bool *visited_;//whether visisted struct
	int max_node_num_;//node count
	std::queue<Node*> nQue_;//the struct used to implement the breadth first traverse 
	
};

LinkGraph::~LinkGraph(){
	delete [] visited_;
	for(int i = 0; i <= max_node_num_; ++i){
		Node * p = graph_[i];
		for(;;){
			Node * del = p;
			if(del == NULL) break;
			p = p->next;
			delete del;
		}
	}
	delete [] graph_;
}

void LinkGraph::DeepFirstTraverse(int index){
	if(!visited_[index]){
		std::cout << graph_[index]->data << " ";
		visited_[index] = true;
	}
	Node *p = graph_[index];
	for(;;){
		p = p->next;
		if(p == NULL) break;
		if(!visited_[p->data])
			DeepFirstTraverse(p->data);
	}
}

void LinkGraph::BreathFirstTraverse(int index){
	if(!visited_[index]){
		std::cout << graph_[index]->data << " ";
		visited_[index] = true;
		nQue_.push(graph_[index]);
	}
	for(;;){
		if(nQue_.empty()) break;
		Node * p = nQue_.front()->next;
		for(;;){
			if(p == NULL) break;
			if(!visited_[p->data]){
				std::cout<< p->data <<" ";
				visited_[p->data] = true;
				nQue_.push(graph_[p->data]);
			}
			p = p->next;
		} 
		nQue_.pop();
	}
}

void LinkGraph::CreatGraph(){
	graph_ = new Node*[max_node_num_+1];
	visited_ = new bool[max_node_num_+1];
	for(int i = 1; i <= max_node_num_; ++i)
		visited_[i] = false;

	Node * p = NULL;
	graph_[0] = NULL;//dummy node
	for(int i = 1; i<= max_node_num_; ++i){
		graph_[i] = new Node;
		graph_[i]->data = i;
		p = graph_[i];
		std::cout <<"Input Vec[" <<i<< "] adjacent node count :" << std::endl;
		int n;
		if(std::cin>>n){
			for(int j = 0 ; j < n; ++j){
				std::cout <<"Input Vec[" <<i << "] adjacent number:" <<std::endl;
				p->next = new Node;
				p = p->next;
				std::cin >> p->data;
			}
		}
		p->next = NULL;
	}
}
#endif